{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Nodes with Even-Valued Grandparent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumEvenGrandparent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #祖父节点值为偶数的节点和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果不存在祖父节点值为偶数的节点，那么返回&nbsp;<code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/10/1473_ex1.png\" style=\"height: 214px; width: 350px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在&nbsp;<code>1</code> 到&nbsp;<code>10^4</code>&nbsp;之间。</li>\n",
    "\t<li>每个节点的值在&nbsp;<code>1</code> 到&nbsp;<code>100</code> 之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-nodes-with-even-valued-grandparent](https://leetcode.cn/problems/sum-of-nodes-with-even-valued-grandparent/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-nodes-with-even-valued-grandparent](https://leetcode.cn/problems/sum-of-nodes-with-even-valued-grandparent/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(node, fa, afa):\n",
    "            if not node:\n",
    "                return\n",
    "            if afa > 0 and afa % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            if node.left: dfs(node.left, node.val, fa)\n",
    "            if node.right: dfs(node.right, node.val, fa)\n",
    "            \n",
    "        dfs(root, -1, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        queue = [[root, False]]\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            for node, isOk in queue:\n",
    "                if node.left:\n",
    "                    new_queue.append([node.left, node.val%2 == 0])\n",
    "                    res += node.left.val if isOk else 0\n",
    "                if node.right:\n",
    "                    new_queue.append([node.right, node.val%2 == 0])\n",
    "                    res += node.right.val if isOk else 0\n",
    "            queue = new_queue\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val & 1 == 0:\n",
    "                    if left := node.left:\n",
    "                        if left.left:\n",
    "                            self.ans += left.left.val\n",
    "                        if left.right:\n",
    "                            self.ans += left.right.val\n",
    "                        \n",
    "                    if right := node.right:\n",
    "                        if right.left:\n",
    "                            self.ans += right.left.val\n",
    "                        if right.right:\n",
    "                            self.ans += right.right.val\n",
    "                        \n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "            \n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def dfs(r,flag):\n",
    "            if not r:\n",
    "                return []\n",
    "            res=[]\n",
    "            if flag==1:\n",
    "                if r.left:\n",
    "                    res+=[r.left.val]\n",
    "                if r.right:\n",
    "                    res+=[r.right.val]\n",
    "\n",
    "            \n",
    "            if r.val%2==0:\n",
    "                flag=2\n",
    "            else:\n",
    "                flag=0\n",
    "            if r.right:\n",
    "                # print(type(r.right))\n",
    "                res+=dfs(r.right,flag-1)\n",
    "            if r.left:\n",
    "                \n",
    "                res+=dfs(r.left,flag-1)\n",
    "            return res\n",
    "        temp=dfs(root,-1)\n",
    "        return sum(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        return self.recurse(root, None, None)\n",
    "    \n",
    "    def recurse(self, node, grandfather, father):\n",
    "        res = 0\n",
    "\n",
    "        if node.left is not None:\n",
    "            res += self.recurse(node.left, father, node)\n",
    "        \n",
    "        if node.right is not None:\n",
    "            res += self.recurse(node.right, father, node)\n",
    "        \n",
    "        if grandfather is not None and grandfather.val & 1 == 0:\n",
    "            res += node.val\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(grandparent, parent, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        \n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(grandparent, parent, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        \n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        self.traverse(root, -1)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, p):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if p % 2 == 0:\n",
    "            if root.left: self.res += root.left.val \n",
    "            if root.right: self.res += root.right.val \n",
    "\n",
    "        self.traverse(root.left, root.val)\n",
    "        self.traverse(root.right, root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(grandparent, parent, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        \n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.helper(root, 1, 1)\n",
    "        return self.res\n",
    "        \n",
    "    def helper(self, root, father, grandfather):\n",
    "        if root:\n",
    "            if grandfather % 2 == 0:\n",
    "                self.res += root.val\n",
    "            grandfather = father\n",
    "            father = root.val\n",
    "            self.helper(root.left, father, grandfather)\n",
    "            self.helper(root.right, father, grandfather)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(gv,pv,node):\n",
    "            if not node:\n",
    "                return\n",
    "            if gv%2==0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(pv,node.val,node.left)\n",
    "            dfs(pv,node.val,node.right)\n",
    "        dfs(1,1,root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node , pre2 , pre1):\n",
    "            if node:\n",
    "                dfs(node.left , pre1 , node.val)\n",
    "                dfs(node.right , pre1 , node.val)\n",
    "            \n",
    "                if not pre2 % 2 and pre2:\n",
    "                    nonlocal ans\n",
    "                    ans += node.val\n",
    "        dfs(root ,0 , 0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val & 1 == 0:\n",
    "                    if left := node.left:\n",
    "                        if left.left:\n",
    "                            self.ans += left.left.val\n",
    "                        if left.right:\n",
    "                            self.ans += left.right.val\n",
    "                        \n",
    "                    if right := node.right:\n",
    "                        if right.left:\n",
    "                            self.ans += right.left.val\n",
    "                        if right.right:\n",
    "                            self.ans += right.right.val\n",
    "                        \n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(grandparent, parent, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        \n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(gp_val, p_val, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if gp_val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(p_val, node.val, node.left)\n",
    "            dfs(p_val, node.val, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(gp_val, p_val, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if gp_val & 1 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(p_val, node.val, node.left)\n",
    "            dfs(p_val, node.val, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(gp_val, p_val, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if gp_val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(p_val, node.val, node.left)\n",
    "            dfs(p_val, node.val, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode, par: TreeNode, anc: TreeNode) -> int:\n",
    "            if root == None:\n",
    "                return 0\n",
    "            else:\n",
    "                v = 0\n",
    "                if anc != None and anc.val % 2 == 0:\n",
    "                    v = root.val \n",
    "                return v + dfs(root.left, root, par) + dfs(root.right, root, par)\n",
    "\n",
    "        return dfs(root, None, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.sum = 0\n",
    "        self.traverse(root)\n",
    "        return self.sum\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val % 2 == 0:\n",
    "            if root.left:\n",
    "                if root.left.left:\n",
    "                    self.sum += root.left.left.val\n",
    "                if root.left.right:\n",
    "                    self.sum += root.left.right.val\n",
    "            \n",
    "            if root.right:\n",
    "                if root.right.left:\n",
    "                    self.sum += root.right.left.val\n",
    "                if root.right.right:\n",
    "                    self.sum += root.right.right.val\n",
    "        \n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode, a: List[int]) -> int:\n",
    "            #print(f'root.val = {root.val}, a = {a}')\n",
    "            b = [x - 1 for x in a]\n",
    "            t = 0\n",
    "            if 0 in b:\n",
    "                t = root.val\n",
    "            if root.val % 2 == 0:\n",
    "                b.append(2) \n",
    "            if root.left != None:\n",
    "                t += dfs(root.left, [x for x in b if x > 0])\n",
    "            if root.right != None:\n",
    "                t += dfs(root.right, [x for x in b if x > 0])\n",
    "            return t\n",
    "        \n",
    "        return dfs(root, [])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(gp_val, p_val, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if gp_val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(p_val, node.val, node.left)\n",
    "            dfs(p_val, node.val, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val & 1 == 0:\n",
    "                    if l := node.left:\n",
    "                        if ll := l.left:\n",
    "                            self.ans += ll.val\n",
    "                        if lr := l.right:\n",
    "                            self.ans += lr.val\n",
    "                        \n",
    "                    if r := node.right:\n",
    "                        if rl := r.left:\n",
    "                            self.ans += rl.val\n",
    "                        if rr := r.right:\n",
    "                            self.ans += rr.val\n",
    "                        \n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "            \n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def dfs(node, p, gp):\n",
    "            if node:\n",
    "                return dfs(node.left, node.val, p) + \\\n",
    "                dfs(node.right, node.val, p) + \\\n",
    "                (0 if gp % 2 != 0 else node.val)\n",
    "            return 0\n",
    "        \n",
    "        return dfs(root, 1, 1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(gp_odd, p_odd, node):\n",
    "            if node:\n",
    "                dfs(p_odd, node.val & 1, node.left)\n",
    "                dfs(p_odd, node.val & 1, node.right)\n",
    "                if not gp_odd:\n",
    "                    self.ans += node.val\n",
    "\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def helper(grandparent,parent,node):\n",
    "            nonlocal res\n",
    "            if node is None:return \n",
    "            if grandparent.val%2==0:\n",
    "                res+=node.val\n",
    "            helper(parent,node,node.left)\n",
    "            helper(parent,node,node.right)\n",
    "        if root.left:\n",
    "            helper(root,root.left,root.left.left)\n",
    "            helper(root,root.left,root.left.right)\n",
    "        if root.right:\n",
    "            helper(root,root.right,root.right.left)\n",
    "            helper(root,root.right,root.right.right)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        path=[]\n",
    "        def helper(node):\n",
    "            nonlocal res\n",
    "            if node is None:return\n",
    "            path.append(node.val)\n",
    "            if len(path)>=3:\n",
    "                if path[-3]%2==0:\n",
    "                    res+=path[-1]\n",
    "            helper(node.left)\n",
    "            helper(node.right)\n",
    "            path.pop()\n",
    "        helper(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(node, fa, afa):\n",
    "            if not node:\n",
    "                return\n",
    "            if afa > 0 and afa % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            if node.left: dfs(node.left, node.val, fa)\n",
    "            if node.right: dfs(node.right, node.val, fa)\n",
    "            \n",
    "        dfs(root, -1, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def dfs(grandparent, parent, node):\n",
    "            \n",
    "            if not node:\n",
    "                return\n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal res\n",
    "                res += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\r\n",
    "        self.res = 0\r\n",
    "        self.traverse(root)\r\n",
    "        return self.res\r\n",
    "    \r\n",
    "    def traverse(self,root):\r\n",
    "        if not root:\r\n",
    "            return \r\n",
    "        if root.val %2:\r\n",
    "            pass\r\n",
    "        else:\r\n",
    "            if root.left:\r\n",
    "                if root.left.left:\r\n",
    "                    self.res += root.left.left.val\r\n",
    "                if root.left.right:\r\n",
    "                    self.res += root.left.right.val\r\n",
    "            if root.right:\r\n",
    "                if root.right.left:\r\n",
    "                    self.res += root.right.left.val\r\n",
    "                if root.right.right:\r\n",
    "                    self.res += root.right.right.val\r\n",
    "        self.traverse(root.left)\r\n",
    "        self.traverse(root.right)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(gp,p,node):\n",
    "            if not node:\n",
    "                return\n",
    "            if gp.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans+=node.val\n",
    "            dfs(p,node,node.left)\n",
    "            dfs(p,node,node.right)\n",
    "\n",
    "        if root.left:\n",
    "            dfs(root,root.left,root.left.left)\n",
    "            dfs(root,root.left,root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root,root.right,root.right.left)\n",
    "            dfs(root,root.right,root.right.right)\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(gp_val, p_val, node):\n",
    "            if node:\n",
    "                if gp_val & 1 == 0:\n",
    "                    nonlocal ans\n",
    "                    ans += node.val\n",
    "                dfs(p_val, node.val, node.left)\n",
    "                dfs(p_val, node.val, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val%2==0:\n",
    "                self.res += dfs2(root)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        def dfs2(root):\n",
    "            total = 0\n",
    "            total+=root.left.left.val if root.left and root.left.left else 0\n",
    "            total+=root.left.right.val if root.left and root.left.right else 0\n",
    "            total+=root.right.left.val if root.right and root.right.left else 0\n",
    "            total+=root.right.right.val if root.right and root.right.right else 0\n",
    "            return total\n",
    "\n",
    "        self.res = 0\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        # 每个节点都加一个父节点\n",
    "        self.ans = 0\n",
    "        def dfs(node, par=None):\n",
    "            if not node:\n",
    "                return\n",
    "            node.par = par\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "\n",
    "            if par and par.par and (par.par.val % 2 == 0):\n",
    "                self.ans += node.val\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        res = [0]\n",
    "        def dfs(root, father, grandfather):\n",
    "            if root:\n",
    "                dfs(root.left, root.val, father)\n",
    "                dfs(root.right, root.val, father)\n",
    "                if grandfather % 2 == 0 and grandfather != 0:\n",
    "                    res[0] += root.val\n",
    "        dfs(root, 0, 0) # 若没有祖父或父亲节点，就初始化为0，因为节点值最小为1\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.sum = 0\n",
    "        self.sumEvenGrandparentWithTrace(root, (1, 1))\n",
    "        return self.sum\n",
    "\n",
    "    sum = 0\n",
    "    def sumEvenGrandparentWithTrace(self, root: TreeNode, parents: Tuple):\n",
    "        if root is None:\n",
    "            return\n",
    "        \n",
    "        self.sumEvenGrandparentWithTrace(root.left, (root.val, parents[0]))\n",
    "        self.sumEvenGrandparentWithTrace(root.right, (root.val, parents[0]))\n",
    "        if parents[1] % 2 == 0:\n",
    "            self.sum += root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        \n",
    "        def dfs(node, parent, grandparent):\n",
    "            if not node: return\n",
    "\n",
    "            if grandparent and grandparent % 2 == 0:\n",
    "                self.ans += node.val\n",
    "\n",
    "            dfs(node.left, node.val, parent)\n",
    "            dfs(node.right, node.val, parent)\n",
    "\n",
    "        dfs(root, None, None)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        queue = deque([root])\n",
    "\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    if node.val % 2 == 0:\n",
    "                        if node.left.left:\n",
    "                            ans += node.left.left.val\n",
    "                        if node.left.right:\n",
    "                            ans += node.left.right.val\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    if node.val % 2 == 0:\n",
    "                        if node.right.left:\n",
    "                            ans += node.right.left.val\n",
    "                        if node.right.right:\n",
    "                            ans += node.right.right.val\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        total = 0\n",
    "        if not root: \n",
    "            return total\n",
    "\n",
    "        if root.val % 2 == 0:\n",
    "            if root.left:\n",
    "                if root.left.left:\n",
    "                    total += root.left.left.val\n",
    "                if root.left.right:\n",
    "                    total += root.left.right.val\n",
    "            if root.right:\n",
    "                if root.right.left:\n",
    "                    total += root.right.left.val\n",
    "                if root.right.right:\n",
    "                    total += root.right.right.val\n",
    "        \n",
    "        return total + self.sumEvenGrandparent(root.left) + self.sumEvenGrandparent(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.sum = 0\n",
    "        \n",
    "        def travel(root, f=0, a=0):\n",
    "            if not root:\n",
    "                return\n",
    "            if a:\n",
    "                self.sum += root.val\n",
    "            if f:\n",
    "                a = 1\n",
    "            else:\n",
    "                a = 0\n",
    "            if root.val % 2 == 0:\n",
    "                f = 1\n",
    "            else:\n",
    "                f = 0\n",
    "            travel(root.left, f, a)\n",
    "            travel(root.right, f, a)\n",
    "        travel(root)\n",
    "        return self.sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                    if node.val%2 == 0:\n",
    "                        if node.left.left:\n",
    "                            ans += node.left.left.val\n",
    "                        if node.left.right:\n",
    "                            ans += node.left.right.val\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "                    if node.val%2 == 0:\n",
    "                        if node.right.left:\n",
    "                            ans += node.right.left.val\n",
    "                        if node.right.right:\n",
    "                            ans += node.right.right.val\n",
    "            stack = tmp\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans=0\n",
    "        def f(r,c1,c2):\n",
    "            nonlocal ans\n",
    "            if r.left:\n",
    "                if c1:\n",
    "                    ans+=r.left.val\n",
    "                if r.left.val&1:\n",
    "                    f(r.left,c2,False)\n",
    "                else:\n",
    "                    f(r.left,c2,True)\n",
    "            if r.right:\n",
    "                if c1:\n",
    "                    ans+=r.right.val\n",
    "                if r.right.val&1:\n",
    "                    f(r.right,c2,False)\n",
    "                else:\n",
    "                    f(r.right,c2,True)\n",
    "        f(root,False,root.val&1==0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        self.traverse(root, -1)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, grandpat):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if grandpat % 2 == 0:\n",
    "            self.res += root.left.val if root.left else 0\n",
    "            self.res += root.right.val if root.right else 0\n",
    "\n",
    "        self.traverse(root.left, root.val)\n",
    "        self.traverse(root.right, root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def D(r, p = False, g = False):\n",
    "            if not r: return 0\n",
    "            return r.val * g + D(r.left, not r.val % 2, p) + D(r.right, not r.val % 2, p)\n",
    "        return D(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(grandparent, parent, node):\n",
    "            if not node:\n",
    "                return \n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(o: TreeNode, fa: int, gp: int) -> None:\n",
    "            nonlocal ans\n",
    "            if not o:\n",
    "                return\n",
    "            if gp % 2 == 0:\n",
    "                ans += o.val\n",
    "\n",
    "            dfs(o.left, o.val, fa)\n",
    "            dfs(o.right, o.val, fa)\n",
    "\n",
    "        dfs(root, 1, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val % 2 == 0:\n",
    "            if root.left:\n",
    "                if root.left.left:\n",
    "                    self.res += root.left.left.val\n",
    "                if root.left.right:\n",
    "                    self.res += root.left.right.val\n",
    "            if root.right:\n",
    "                if root.right.left:\n",
    "                    self.res += root.right.left.val\n",
    "                if root.right.right:\n",
    "                    self.res += root.right.right.val\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ret =0\n",
    "        def dfs(node,father_value):\n",
    "            nonlocal ret\n",
    "            adder = 0\n",
    "            if father_value % 2 == 0:\n",
    "                adder = 1\n",
    "            if node.left is not None:\n",
    "                ret += node.left.val * adder\n",
    "                dfs(node.left,node.val)\n",
    "            if node.right is not None:\n",
    "                ret += node.right.val * adder\n",
    "                dfs(node.right,node.val)\n",
    "        dfs(root, 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def dfs(cur, grand, parent):\n",
    "            if not cur:\n",
    "                return 0\n",
    "            if grand != 0 and grand %2 == 0:\n",
    "                status = True\n",
    "            else:\n",
    "                status = False\n",
    "            if parent == 0:\n",
    "                parent = cur.val\n",
    "            else:\n",
    "                grand = parent\n",
    "                parent = cur.val\n",
    "            if status:\n",
    "                return cur.val + dfs(cur.left, grand, parent) + dfs(cur.right, grand, parent)\n",
    "            else:\n",
    "                return dfs(cur.left, grand, parent) + dfs(cur.right, grand, parent)\n",
    "        return dfs(root, 0, 0)\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        d=deque([root])\n",
    "        special=[]\n",
    "        ans=0\n",
    "        while d:\n",
    "            sz=len(d)\n",
    "            for i in range(sz):\n",
    "                curr=d.popleft()\n",
    "                if curr.val%2==0:\n",
    "                    if curr.left:\n",
    "                        special.append(curr.left)\n",
    "                    if curr.right:\n",
    "                        special.append(curr.right)\n",
    "                if curr.left:\n",
    "                    d.append(curr.left)\n",
    "                if curr.right:\n",
    "                    d.append(curr.right)\n",
    "        for s in special:\n",
    "            if s.left:\n",
    "                ans+=s.left.val\n",
    "            if s.right:\n",
    "                ans+=s.right.val\n",
    "\n",
    "        return ans       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(grandparent, parent, node):\n",
    "            if not node:\n",
    "                return\n",
    "            if grandparent.val % 2 == 0:\n",
    "                nonlocal ans\n",
    "                ans += node.val\n",
    "            dfs(parent, node, node.left)\n",
    "            dfs(parent, node, node.right)\n",
    "        \n",
    "        if root.left:\n",
    "            dfs(root, root.left, root.left.left)\n",
    "            dfs(root, root.left, root.left.right)\n",
    "        if root.right:\n",
    "            dfs(root, root.right, root.right.left)\n",
    "            dfs(root, root.right, root.right.right)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        result = 0\n",
    "        mapping = dict()\n",
    "\n",
    "        '''\n",
    "                    6\n",
    "                7       8\n",
    "            2     7    1     3\n",
    "        9       1   4           5\n",
    "        '''\n",
    "\n",
    "        def dfs(root, parent):\n",
    "            nonlocal result\n",
    "            if root is None:\n",
    "                return\n",
    "            mapping[root] = parent\n",
    "            if mapping[root] and mapping.get(mapping[root]) and mapping.get(mapping[root]).val % 2 == 0:\n",
    "                result += root.val\n",
    "            dfs(root.left, root)\n",
    "            dfs(root.right, root)\n",
    "\n",
    "        dfs(root, None)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(gp_odd, p_odd, node):\n",
    "            if node:\n",
    "                if not gp_odd:\n",
    "                    self.ans += node.val\n",
    "                dfs(p_odd, node.val & 1, node.left)\n",
    "                dfs(p_odd, node.val & 1, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        answer = 0\n",
    "        def dfs(gp_val, p_val, node):\n",
    "            nonlocal answer\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            if gp_val%2==0:\n",
    "                answer += node.val\n",
    "            dfs(p_val, node.val, node.left)\n",
    "            dfs(p_val, node.val, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return answer\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(gp_odd, p_odd, node):\n",
    "            if node:\n",
    "                dfs(p_odd, (val := node.val) & 1, node.left)\n",
    "                dfs(p_odd, val & 1, node.right)\n",
    "                if not gp_odd:\n",
    "                    self.ans += val\n",
    "\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        self.search(root)\n",
    "        return self.ans\n",
    "    \n",
    "    def search(self, root, status = 0):\n",
    "        if not root:\n",
    "            return 0\n",
    "        if status & 1:\n",
    "            self.ans += root.val\n",
    "        status >>= 1\n",
    "        if not root.val & 1:\n",
    "            status |= 2\n",
    "        self.search(root.left, status)\n",
    "        self.search(root.right, status)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(gp_odd, p_odd, node):\n",
    "            if node:\n",
    "                if not gp_odd:\n",
    "                    self.ans += node.val\n",
    "                dfs(p_odd, node.val & 1, node.left)\n",
    "                dfs(p_odd, node.val & 1, node.right)\n",
    "        \n",
    "        dfs(1, 1, root)\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        if root.left:\n",
    "            res += self.sumEvenGrandparent(root.left)\n",
    "            if root.val %2 == 0:\n",
    "                if root.left.left:\n",
    "                    res += root.left.left.val\n",
    "                if root.left.right:\n",
    "                    res += root.left.right.val\n",
    "\n",
    "            \n",
    "        if root.right:\n",
    "            res += self.sumEvenGrandparent(root.right)\n",
    "            if root.val %2 == 0:\n",
    "                if root.right.left:\n",
    "                    res += root.right.left.val\n",
    "                if root.right.right:\n",
    "                    res += root.right.right.val\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        return self.go(root, -1, -1)\n",
    "    \n",
    "    def go(self, node, father, g_father):\n",
    "        if not node:\n",
    "            return 0\n",
    "        sum_ = self.go(node.left, node.val, father) + self.go(node.right, node.val, father)\n",
    "        if g_father % 2 == 0:\n",
    "            sum_ += node.val\n",
    "        return sum_\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res=0\n",
    "\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        def recursion(root:TreeNode,lev2:int,lev1:int):\n",
    "            if root:\n",
    "                recursion(root.left,lev1,root.val)\n",
    "                recursion(root.right,lev1,root.val)\n",
    "\n",
    "                if lev2%2==0 and lev2!=0:\n",
    "                    self.res +=root.val\n",
    "                    \n",
    "        recursion(root,0,0)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node, parent, grand):\n",
    "            if not node:\n",
    "                return\n",
    "            if grand:\n",
    "                self.res += node.val\n",
    "            \n",
    "            dfs(node.left, node.val % 2 == 0, parent)\n",
    "            dfs(node.right, node.val % 2 == 0, parent)\n",
    "        dfs(root, False, False)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        sum_ = 0\n",
    "        if not root:return sum_\n",
    "        qeque = deque()\n",
    "        qeque.append((root,0,0))\n",
    "\n",
    "        while qeque:\n",
    "            cur = qeque.popleft()\n",
    "            # print(cur[0].val,cur[1],cur[2])\n",
    "            if cur[2]:\n",
    "                 sum_ += cur[0].val\n",
    "            # print(cur[0].val,cur[1])\n",
    "            # print(\"\\n-----------------------------------------\")\n",
    "            a = 1 if cur[0].val%2 == 0 else 0\n",
    "            b = 1 if cur[1] else 0\n",
    "\n",
    "            if cur[0].left:\n",
    "                qeque.append((cur[0].left,a,b))\n",
    "            if cur[0].right:\n",
    "                qeque.append((cur[0].right,a,b))\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        self.result = 0\n",
    "        self.son(root, 0)\n",
    "        return self.result\n",
    "        \n",
    "\n",
    "    def son(self, current, parent_value):\n",
    "        if not current:\n",
    "            return\n",
    "        if current.left:\n",
    "            if parent_value % 2 == 0 and parent_value > 0:\n",
    "                self.result += current.left.val\n",
    "            self.son(current.left, current.val)\n",
    "        if current.right:\n",
    "            if parent_value % 2 == 0 and parent_value > 0:\n",
    "                self.result += current.right.val\n",
    "            self.son(current.right, current.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumEvenGrandparent(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        row = [(root, 0)]\n",
    "        while row:\n",
    "            nrow = []\n",
    "            for node, status in row:\n",
    "                if status & 1:\n",
    "                    ans += node.val\n",
    "                status >>= 1\n",
    "                if not node.val & 1:\n",
    "                    status |= 2\n",
    "                for child in (node.left, node.right):\n",
    "                    if child:\n",
    "                        nrow.append((child, status))\n",
    "            row = nrow\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
